#include <stdio.h>
#include <stdlib.h>

typedef struct LNode
{
    int data;
    LNode *next;
} LNode, *LinkList;

// bool InitList(LinkList &L); // 初始化
// //void ClearList(LinkList &L);                 // 销毁
// bool ListEmpty(LinkList L);                  // 判空
// int ListLength(LinkList L);                  // 长度
// LNode *GetElem(LinkList L, int i);           // 按位查找
// LNode *LocateElem(LinkList L, int e);        // 按值查找
// bool InsertAfter(LNode *p, LNode *s);        //后插法
// bool InsertPrior(LNode *p, LNode *s);        //前插法(在后插的基础上)
// bool ListInsert(LinkList &L, int i, int e);  // 插入
// bool ListDelete(LinkList &L, int i, int &e); // 删除
// bool PrintList(LinkList L);                  // 输出

//初始化单链表
bool InitList(LinkList &L)
{
    L = (LinkList)malloc(sizeof(LNode));
    if (L == NULL)
        return false;
    L->next = NULL;
    return true;
}

//判空
bool ListEmpty(LinkList L)
{
    if (L)
        return false;
    else
        return true;
}

//长度
int ListLength(LinkList L)
{
    LNode *p;
    p = L->next;
    int length = 0;
    while (p)
    {
        length++;
        p = p->next;
    }
    return length;
}

//按位查找
LNode *GetElem(LinkList L, int i)
{
    if (!L->next || i < 0)
        return NULL;
    int j = 1;
    LNode *p;
    p = L->next;
    while (j < i && p)
    {
        p = p->next;
        j++;
    }
    return p;
}

//按值查找
LNode *LocateElem(LinkList L, int e)
{
    if (!L)
        return NULL;
    LNode *p;
    p = L->next;
    while (p && p->data != e)
    {
        p = p->next;
    }
    return p;
}

//后插法
bool InsertAfter(LNode *p, LNode *s)
{
    if (!p || !s)
        return false;
    p->next = s;
    s->next = NULL;
    return true;
}

//前插法(在后插的基础上)
bool InsertPrior(LNode *p, LNode *s)
{
    if (!p || !s)
        return false;
    s->next = p->next;
    p->next = s;
    int t = p->data;
    p->data = s->data;
    s->data = t;
    return true;
}

//插入
bool ListInsert(LinkList &L, int i, int e)
{
    LNode *p, *s;
    s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    p = GetElem(L, i - 1);
    return InsertPrior(p, s);
}

// 删除
bool ListDelete(LinkList &L, int i, int &e)
{
    LNode *p, *s;
    p = GetElem(L, i - 1);
    s = GetElem(L, i);
    e = s->data;
    p->next = s->next;
    free(s);
    // 改 没有返回值
    return true;
}

// 输出
bool PrintList(LinkList L)
{
    LNode *p;
    p = L->next;
    int j = 1;
    while (p)
    {
        printf("LinkList_L[%d] = %d\n", j, p->data);
        p = p->next;
        j++;
    }

    // 改 没有返回值
    return true;
}

bool ReverseList(LinkList &L)
{
    LNode *s;
    s = (LinkList)malloc(sizeof(LNode));
    LNode *p, *pre; //pre保证链不丢
    p = L->next;
    s->next = p; //先形成有一个节点的链
    p = p->next; //p指向第二个结点
    pre = p->next;

    s->next->next = NULL; // 修: 这里需要断链 否则会死循环

    while (pre) // 修: 这个指针虽然叫做pre 但在遍历过程中 是走在最前面的 所以需要先判断pre是否为空
                //     否则会出现空指针异常
    //while (p)
    {
        p->next = s->next;
        s->next = p; //前插法
        p = pre;     //移动工作结点
        pre = pre->next;
    }
    // 在每一次循环中 p是插入的节点 而pre = pre->next在插入之后
    // 也就是说 当运行至 pre == NULL 退出循环时 仍然还有一个p节点 未执行插入
    // 这里添加一下
    p->next = s->next; // 修
    s->next = p;       // 修

    L = s;
    return true;
}

// 优化
// 上面的方法中有两个比较明显的问题
//  1. p = L->next; p = p->next; pre = p->next;
//     代码中的这段意味着链表最小也需要是 L->next->next->next->null 的长度 小于这个长度会出现空指针异常
//  2. 插入操作 位于遍历操作之后 会导致循环退出还剩一个的情况
//     把两个操作调换位置可以解决这个问题
// 优化以后的方法如下 :
bool ReverseList2(LinkList &L)
{
    // 新链头结点
    LNode *s = (LinkList)malloc(sizeof(LNode));
    s->next = NULL;


    LNode *p,*pre;       

    LNode *p, *pre;


    p = L->next;
    while (p)
    {
        pre = p;
        p = p->next;

        pre->next = s->next;
        s->next = pre;
    }
    L = s;            //返回链表头
    return true;
}

// 上面的方法还留有一个问题
// s 是新申请的头节点 并重新赋值给L返回
// 但原本的L头结点申请的空间没有被释放 会导致内存泄露
// 复用头结点L可以解决这个问题
// 完善如下
void ReverseList3(LinkList &L)
{
    LNode *head = NULL; // 新链第一个节点
    LNode *p = L->next; // 遍历指针
    LNode *temp;        // 临时变量
    while (p != NULL)
    {

        temp = p->next; // 暂存p的下一个节点 因为之后p会前插导致锻链
        p->next = head; // 前插操作//
        head = p;       // head始终记录第一个结点
        p = temp;       // p继续遍历

        temp = p;          // 暂存当前需要插入的节点
        p = p->next;       // p向后遍历
        temp->next = head; // 执行插入
        head = temp;       // head 始终指向第一个接地那

    }
    L->next = head; // 重新赋值给L
}

int main()
{
    LinkList L;
    InitList(L);
    LNode *s1 = (LNode *)malloc(sizeof(LNode));
    s1->data = 1;
    InsertAfter(L, s1);
    LNode *s2 = (LNode *)malloc(sizeof(LNode));
    s2->data = 2;
    InsertAfter(s1, s2);
    LNode *s3 = (LNode *)malloc(sizeof(LNode));
    s3->data = 3;
    s3->next = NULL;
    InsertAfter(s2, s3);
    PrintList(L);

    printf("\n");
    LNode *node = GetElem(L, 2);
    printf("the second is ==> %d\n", node->data);
    node = LocateElem(L, 2);
    printf("the node of 2 is==> %d\n", node->data);

    // ListInsert(L, 3, 4);
    // PrintList(L);
    // printf("\n");

    // int e;
    // ListDelete(L, 3, e);
    // printf("delete the third ==> %d\n", e);
    // PrintList(L);
    // printf("\n");

    //ReverseList(L);
    //PrintList(L);
    printf("===before reverse===\n");
    PrintList(L);
    ReverseList3(L);
    printf("===after reverse ===\n");
    PrintList(L);
    printf("\n");

    return 0;
}
